#include <iostream>
#include "BinaryTree.h"
using namespace std;

int main( )
{
    /*
    * test BinarySearchTree
    */
    BinarySearchTree<int> a;
    int NUMS1 = 400000;
    const int GAP1  =   3711;
    int i;

    cout << "Checking BinarySearchTree... (no more output means success)" << endl;

    for( i = GAP1; i != 0; i = ( i + GAP1 ) % NUMS1 )
        a.insert( i );

    for( i = 1; i < NUMS1; i+= 2 )
        a.remove( i );

    if( NUMS1 < 40 )
        a.printTree( );
    if( a.findMin( ) != 2 || a.findMax( ) != NUMS1 - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS1; i+=2 )
        if( !a.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS1; i+=2 )
    {
        if( a.contains( i ) )
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> a2;
    a2 = a;

    for( i = 2; i < NUMS1; i+=2 )
        if( !a2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS1; i+=2 )
    {
        if( a2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished testing BinarySearchTree" << endl;

    /*
    * test AvlTree
    */
    AvlTree<int> b;
    int NUMS2 = 2000000;
    const int GAP2  =   37;

    cout << "Checking AvlTree... (no more output means success)" << endl;

    for( i = GAP2; i != 0; i = ( i + GAP2 ) % NUMS2 )
        b.insert( i );
    b.remove( 0 );
    for( i = 1; i < NUMS2; i += 2 )
        b.remove( i );

    if( NUMS2 < 40 )
        b.printTree( );
    if( b.findMin( ) != 2 || b.findMax( ) != NUMS2 - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS2; i += 2 )
        if( !b.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS2; i += 2 )
    {
        if( b.contains( i )  )
            cout << "Find error2!" << endl;
    }

    AvlTree<int> b2;
    b2 = b;

    for( i = 2; i < NUMS2; i += 2 )
        if( !b2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS2; i += 2 )
    {
        if( b2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "End of test AvlTree..." << endl;

    /*
    *TESTING RedBlackTree
    */
    const int NEG_INF = -9999;
    RedBlackTree<int> c{ NEG_INF };
    int NUMS3 = 400000;
    const int GAP3  =   37;

    cout << "Checking RedBlackTree... (no more output means success)" << endl;

    for( i = GAP3; i != 0; i = ( i + GAP3 ) % NUMS3 )
        c.insert( i );

    if( NUMS3 < 40 )
        c.printTree( );
    if( c.findMin( ) != 1 || c.findMax( ) != NUMS3 - 1 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 1; i < NUMS3; ++i )
        if( !c.contains( i ) )
            cout << "Find error1!" << endl;
    if( c.contains( 0 ) )
        cout << "Oops!" << endl;

    
    RedBlackTree<int> c2{ NEG_INF };
    c2 = c;

    for( i = 1; i < NUMS3; ++i )
        if( !c2.contains( i ) )
            cout << "Find error1!" << endl;
    if( c2.contains( 0 ) )
        cout << "Oops!" << endl;

    cout << "Test RedBlackTree complete ..." << endl;

    /*
    *Testing SplayTree
    */
    SplayTree<int> d;
    int NUMS4 = 30000;
    const int GAP4  =   37;

    cout << "Checking SplayTree... (no more output means success)" << endl;

    for( i = GAP4; i != 0; i = ( i + GAP4 ) % NUMS4 )
        d.insert( i );

    for( i = 1; i < NUMS4; i+= 2 )
        d.remove( i );

    if( NUMS4 < 40 )
        d.printTree( );
    if( d.findMin( ) != 2 || d.findMax( ) != NUMS4 - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS4; i+=2 )
        if( !d.contains( i ) )
            cout << "Find error1!" << endl;
    for( i = 1; i < NUMS4; i+=2 )
    {
        if( d.contains( i ) )
            cout << "Find error2!" << endl;
    }

    SplayTree<int> d2;
    d2 = d;

    for( i = 2; i < NUMS4; i+=2 )
        if( !d2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS4; i+=2 )
    {
        if( d2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Test SplayTree completed." << endl;
    return 0;
}
